/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/submatrix-sum
   @Language: C++
   @Datetime: 19-03-19 15:38
   */

// Time O(n^3), 301ms
class Solution {
public:
	/*
	 * @param matrix: an integer matrix
	 * @return: the coordinate of the left-up and right-down number
	 */
	vector<vector<int>> submatrixSum(vector<vector<int>> &matrix) {
		// write your code here
		if(matrix.size()==0 || matrix[0].size()==0) return {{}};
		int row=matrix.size(), col=matrix[0].size();
		for(int c=0; c<col; c++){
			vector<int> sumrow(row,0);
			for(int i=c; i<col; ++i){
				for(int r=0; r<row; ++r)
					sumrow[r] += matrix[r][i];
				unordered_map<int,int> sums={{0,-1}};   // sum, row
				for(int r=0,sum=0; r<row; r++){
					sum += sumrow[r];
					if(sums.find(sum)!=sums.end()) 
						return {{sums[sum]+1,c},{r,i}};
					sums[sum]=r;
				}
			}
		}
		return {{}};
	}
};
